Various topologies are known in the art for connecting network switches to one another in packet networks. Two example topologies are referred to as Fat-Tree and Dragonfly topologies. Fat-Tree networks were originally defined by Leiserson in “Fat-Trees: Universal Networks for Hardware Efficient Supercomputing,” IEEE Transactions on Computers, volume C-34, no. 10, 1985, pages 892-901, which is incorporated herein by reference.
Öhring, et al., define extended and generalized Fat Trees, in “On Generalized Fat Trees,” Proceedings of the 9th International Symposium on Parallel Processing, 1995, page 37, which is incorporated herein by reference. Routing over Fat Tree topologies is addressed, for example, by Zahavi, in “D-Mod-K Routing Providing Non-Blocking Traffic for Shift Permutations on Real Life Fat Trees,” CCIT Technical Report #776, Technion—Israel Institute of Technology, Haifa, Israel, August, 2010, which is incorporated herein by reference; and by Yuan et al., in “Oblivious Routing for Fat-Tree Based System Area Networks with Uncertain Traffic Demands,” ACM SIGMETRICS Performance Evaluation Review, New York, N.Y., 2007, pages 337-348, which are incorporated herein by reference.
Dragonfly network configurations are addressed, for example, by Matsuoka, in “You Don't Really Need Big Fat Switches Anymore—Almost,” Information Processing Society of Japan (IPSJ) Journal, 2008; and by Kim et al., in “Technology-Driven, Highly-Scalable Dragonfly Topology,” 35th International Symposium on Computer Architecture, 2008, pages 77-78, which are incorporated herein by reference.
Some network elements apply Adaptive Routing (AR) techniques that take into account the current network traffic state. AR in Dragonfly networks is addressed, for example, by Jiang et al., in “Indirect Adaptive Routing on Large Scale Interconnection Networks,” ACM SIGARCH Computer Architecture News, New York, N.Y., 2009, pages 220-231, which is incorporated herein by reference. AR in Fat-Tree networks is addressed by Minkenberg et al., in “Adaptive Routing in Data Center Bridges,” Proceedings of the 2009 17th IEEE Symposium on High Performance Interconnects, Washington, D.C., 2009, pages 33-41, which is incorporated herein by reference.